//
//  LeetcodeQuestions.cpp
//  CppDemo
//
//  Created by 蒋益杰 on 16/9/9.
//  Copyright © 2016年 com.ed. All rights reserved.
//

#include "LeetcodeQuestions.hpp"

#include <unordered_map>
#include <unordered_set>
#include <math.h>
#include <list>
#include <queue>
#include <stack>
#include <sstream>

#include <iostream>
#include <limits.h>

using namespace std;
/**
 *  
 
 "0" => true
 " 0.1 " => true
 "abc" => false
 "1 a" => false
 "2e10" => true
 
 */
bool isNumber(string s) {
    
    return true;
}

int getSum(int a, int b) {
    while(b)
    {
        int carry = a & b;
        a = a ^ b;
        b = carry << 1;
    }
    return a;
}

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> map;

    for(auto it  = nums1.begin(); it != nums1.end(); it++)
    {
        map[*(it)]++;
    }
    
    vector<int> result;
    for(auto it  = nums2.begin(); it != nums2.end(); it++)
    {
        if (map[*it] != 0) {
            result.push_back(*(it));
            map[*it] = 0;
        }
    }
    return result;
}

vector<int> plusOne(vector<int>& digits) {
    int i = 0;
    for (i = digits.size() - 1; i >= 0; --i) {
        if (digits[i] != 9) {
            ++digits[i];
            return digits;
        } else {
            digits[i] = 0;
        }
    }
    if (i < 0) {
        digits.insert(digits.begin(), 1);
    }
    
    return digits;
}

char findTheDifference(string s, string t) {
    unordered_map<char, int> map;
    for (auto it = s.begin(); it != s.end(); it++) {
        map[*it]++;
    }
    
    for (auto it = t.begin(); it != t.end(); it++) {
        if (map[*it] != 0) {
            --map[*it];
            if (map[*it] == 0) {
                map.erase(*it);
            }
        }
    }
    return map.begin()->first;
}

int firstUniqChar(string s) {
    unordered_map<char, int> map;
    for (auto it = s.begin(); it != s.end(); it++) {
        map[*it]++;
    }
    
    size_t count = s.size();
    int idx = -1;
    for (int i = 0; i < count; i++) {
        if (map[s[i]] == 1) {
            idx = i;
            break;
        }
    }
    return idx;
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (headA == NULL || headB == NULL) {
        return NULL;
    }
    ListNode *p1 = headA;
    ListNode *p2 = headB;
    
    int count1 = 1;
    int count2 = 1;
    while (p1->next != NULL) {
        p1 = p1->next;
        count1++;
    }
    
    while (p2->next != NULL) {
        p2 = p2->next;
        count2++;
    }
    if (p1 != p2) {
        return NULL;
    }
    
    if (count1 > count2) {
        for (int i = 0; i < count1 - count2; i++) {
            headA = headA->next;
        }
    } else if (count2 > count1) {
        for (int i = 0; i < count2 - count1; i++) {
            headB = headB->next;
        }
    }
    
    while (headA != headB) {
        headB = headB->next;
        headA = headA->next;
    }
    return headA;
}

vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> paths;
    return paths;
}

int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
    int area = (C - A) * (D - B) + (G - E) * (H - F);
    if (C <= E || G <= A || B >= H || D <= F) {
        return area;
    }
    
    int top = min(D, H);
    int bottom = max(B, F);
    int left = max(A, E);
    int right = min(C, G);
    
    return area - (right - left) * (top - bottom);
}

void reverse1(vector<int> &s, int start, int end) {
    int j = end, i = start;
    if (j < i) {
        return;
    }
    for (; i <= (start + (end - start) / 2); i++) {
        std::swap(s[i], s[j]);
        j--;
    }
}

void rightshfit(vector<int> &s, int num_to_shift) {
    int size = s.size();
    reverse1(s, 0, size - num_to_shift - 1);
    reverse1(s, size - num_to_shift, size - 1);
    reverse1(s, 0, size - 1);
}


vector<int> singleNumber(vector<int>& nums) {
    unordered_map<int, int> map;
    vector<int> res;
    for (auto it = nums.begin(); it != nums.end(); it++) {
        map[*it]++;
    }
    
    for (auto it = map.begin(); it != map.end(); it++) {
        if (it->second == 1) {
            res.push_back(it->first);
        }
    }
    return res;
}


string removeDuplicateLetters(string s) {
    unordered_map<char, int> map;
    for (auto it = s.begin(); it != s.end(); it++) {
        map[*it]++;
    }
    
    string res;
    for (auto it = s.begin(); it != s.end(); it++) {
        if (map[*it] > 1) {
            map[*it]--;
            if (map[*it] == 0) {
                res.push_back(*it);
            }
        } else if (map[*it] == 1 ){
            res.push_back(*it);
        }
    }
    return res;
}

#pragma mark - get last common parent
bool GetNodePath(TreeNode *pRoot, TreeNode *pNode, list<TreeNode *> &path) {
    if (pRoot == pNode) {
        return true;
    }
    
    path.push_back(pRoot);
    bool found = false;
//    auto iterator = pRoot->m_v
    
    return found;
}

TreeNode *GetLastCommonNode(const list<TreeNode *>& path1, const list<TreeNode *>& path2) {
    auto iterator1 = path1.begin();
    auto iterator2 = path2.begin();
    
    TreeNode *pLast = NULL;
    while (iterator1 != path1.end() && iterator2 != path2.end()) {
        if (*iterator1 == *iterator2) {
            pLast = *iterator1;
        }
        iterator1++;
        iterator2++;
    }
    return pLast;
}

vector<int> rightSideView(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) {
        return result;
    }
    queue<TreeNode *> queueNodes;
    queueNodes.push(root);
    TreeNode *curr = root;
    while (queueNodes.size() > 0) {
        size_t curSize = queueNodes.size();
        for (int i = 0; i < curSize; ++i) {
            curr = queueNodes.front();
            queueNodes.pop();
            if (curr->left) {
                queueNodes.push(curr->left);
            }
            if (curr->right) {
                queueNodes.push(curr->right);
            }
        }
        result.push_back(curr->val);
    }
    
    return result;
}

RandomListNode *copyRandomList(RandomListNode *head) {
    if (!head) {
        return head;
    }
    unordered_map<RandomListNode *, RandomListNode *> map;
    stack<RandomListNode *> stk;
    
    RandomListNode *head_copy = new RandomListNode(head->label);
    map[head] = head_copy;
    stk.push(head);
    
    //head random node
    if (head->random) {
        RandomListNode *head_random_copy = new RandomListNode(head->random->label);
        map[head->random] = head_random_copy;
        head_copy->random = head_random_copy;
    }
    
    while (!stk.empty()) {
        RandomListNode *top = stk.top();
        stk.pop();
        
        RandomListNode *copy_node = map[top];
        if (!copy_node) {
            copy_node = new RandomListNode(top->label);
            map[top] = copy_node;
        } else {
            if (top->next) {
                stk.push(top->next);
            }
        }
        
        RandomListNode *next_copy = map[top->next];
        if (top->next && !next_copy) {
            next_copy = new RandomListNode(top->next->label);
            map[top->next] = next_copy;
        }
        copy_node->next = next_copy;
        
        RandomListNode *random_copy = map[top->random];
        if (top->random && !random_copy) {
            random_copy = new RandomListNode(top->random->label);
            map[top->random] = random_copy;
        }
        copy_node->random = random_copy;
    }
    
    return head_copy;
}

TreeNode* buildTree(ListNode *&node, int start, int end) {
    if (start > end) {
        return nullptr;
    }
    int mid = start + (end - start) / 2;
    
    TreeNode *left = buildTree(node, start, mid - 1);
    TreeNode *root = new TreeNode(node->val);
    root->left = left;
    node = node->next;
    root->right = buildTree(node, mid + 1, end);
    return root;
}

TreeNode* sortedListToBST(ListNode* head) {
    ListNode *p = head;
    int size = 0;
    while (p) {
        p = p->next;
        ++size;
    }
    return buildTree(head, 0, size - 1);
}

int findMin(vector<int>& nums) {
    int count = nums.size();
    int result = INT_MAX;
    
    int start = 0, end = count - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (nums[start] <= nums[end]) {
            return min(nums[start], result);
        } else {
            if (nums[mid] >= nums[start]) {
                start = mid + 1;
            } else {
                result = nums[mid];
                end = mid - 1;
            }
        }
    }
    return result;
}

int splitArray(vector<int>& nums, int m) {
    return 0;
}

string Codec::serialize(TreeNode *root) {
    string result;
    if (!root) {
        return result;
    }
    
    queue<TreeNode *> queue_node;
    queue_node.push(root);
    
    //广度优先遍历
    while (!queue_node.empty()) {
        TreeNode *front = queue_node.front();
        queue_node.pop();
        if (front) {
            result.append(to_string(front->val));
            result.append(" ");
            queue_node.push(front->left);
            queue_node.push(front->right);
        } else {
            result.append("# ");
        }
    }
    return result;
}

TreeNode * Codec::deserialize(string data) {
    if (data.empty()) {
        return nullptr;
    }
    istringstream is(data);
    queue<TreeNode *> queue;
    string val;
    is >> val;
    
    TreeNode *root = new TreeNode(stoi(val));
    queue.push(root);
    
    while (!queue.empty()) {
        TreeNode *front = queue.front();
        queue.pop();
        
        if (!(is >> val)) break;
        if (val != "#") {
            TreeNode *left = new TreeNode(stoi(val));
            queue.push(left);
            front->left = left;
        }
        
        if (!(is >> val)) break;
        if (val != "#") {
            TreeNode *right = new TreeNode(stoi(val));
            queue.push(right);
            front->right = right;
        }
    }
    return root;
}

bool isMatch(string s, string p) {
    const char *schar = s.c_str();
    const char *pchar = p.c_str();
    
    
    
    return false;
}

//[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
    vector<pair<int, int>> res;
    sort(people.begin(), people.end(), [](pair<int, int> p1, pair<int, int> p2) {
        return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second);
    });
    for (auto item : people) {
        res.insert(res.begin() + item.second, item);
    }
    return res;
}


UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
    if (!node) {
        return nullptr;
    }
    
    unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> map;
    stack<UndirectedGraphNode *> stk;
    stk.push(node);
    
    UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);
    map[node] = newNode;
    
    while (!stk.empty()) {
        UndirectedGraphNode *top = stk.top();
        stk.pop();
        
        auto copy_node = map[top];
        for (auto neighbor : top->neighbors) {
            auto copy_neighbor = map[neighbor];
            if (!copy_neighbor) {
                stk.push(neighbor);
                copy_neighbor = new UndirectedGraphNode(neighbor->label);
                map[neighbor] = copy_neighbor;
            }
            copy_node->neighbors.push_back(copy_neighbor);
        }
    }
    return newNode;
}

/*
 ["eat", "tea", "tan", "ate", "nat", "bat"]
 
 [
    ["ate", "eat","tea"],
    ["nat","tan"],
    ["bat"]
 ]
 
 */
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string>> result;
    unordered_map<string, int> map;
    
    int index = 0;
    for (auto str : strs) {
        string tmpstr = str;
        sort(str.begin(), str.end());
        
        auto it = map.find(str);
        if (it == map.end()) {
            //不存在
            map[str] = index;
            
            vector<string> items;
            result.push_back(items);
            items.push_back(tmpstr);
        } else {
            auto items = result[map[str]];
            items.push_back(tmpstr);
        }
        index++;
    }
    
    for (auto veccc : result) {
        cout << veccc.size() << endl;
        for (auto str : veccc) {
            cout << str << ", ";
        }
        cout << endl;
    }
    return result;
}


void replaceBlank(char string[], int length) {
    if (string == nullptr || length <= 0) {
        return;
    }
    
    int originalLength = 0;
    int numberOfBlank = 0;
    
    int i = 0;
    while (string[i] != '\0') {
        ++originalLength;
        if (string[i] == ' ') {
            ++numberOfBlank;
        }
        ++i;
    }
    
    int newLength = originalLength + 2 * numberOfBlank;
    if (numberOfBlank > length) {
        return;
    }
    
    int indexOfOriginal = originalLength;
    int indexOfNew = newLength;
    
    while (indexOfOriginal >= 0 && indexOfNew > indexOfOriginal) {
        if (string[indexOfOriginal] == ' ') {
            string[indexOfNew--] = '0';
            string[indexOfNew--] = '2';
            string[indexOfNew--] = '%';
        } else {
            string[indexOfNew--] = string[indexOfOriginal];
        }
        
        --indexOfOriginal;
    }
}

#pragma mark - kmp
void makeNext(const char p[], int next[]) {
    if (p == NULL) {
        return;
    }
    int q, k;
    size_t length = strlen(p);
    next[0] = 0;
    for (q = 1, k = 0; q < length; q++) {
        while (k > 0 && p[q] != p[k]) {
            k = next[k - 1];
        }
        
        if (p[q] == p[k]) {
            k++;
        }
        next[q] = k;
    }
}

int kmp(const char src[], const char p[], int next[]) {
    size_t srcLen = 0, patternLen = 0;
    srcLen = strlen(src);
    patternLen = strlen(p);
    makeNext(p, next);
    for (int i = 0, q = 0; i < srcLen; i++) {
        while (q > 0 && p[q] != src[i]) {
            q = next[q - 1];
        }
        if (p[q] == src[i]) {
            q++;
        }
        
        if (q == patternLen) {
            cout << "Pattern occurs with shift: " << i - patternLen + 1 << " " << endl;
            return static_cast<int>(i - patternLen + 1);
        }
    }
    return -1;
}

bool wordBreak(string s, vector<string>& wordDict) {
    size_t len = s.size();
    vector<bool> dp(len + 1, false);
    dp[0] = true;
    
    for(int i = 0; i < len + 1; ++i) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && find(wordDict.begin(), wordDict.end(), s.substr(j, i - j)) != wordDict.end()) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[len];
}

#pragma mark - edit distance 
int calculateEditDistance(string strA, int pABegin, int pAEnd,
                          string strB, int pBBegin, int pBEnd) {
    if (pABegin > pAEnd) {
        if (pBBegin > pBEnd) {
            return 0;
        }
        return pBEnd - pBBegin + 1;
    }
    
    if (pBBegin > pBEnd) {
        if (pABegin > pAEnd) {
            return 0;
        }
        return pAEnd - pABegin + 1;
    }
    
    if (strA[pABegin] == strB[pBBegin]) {
        return calculateEditDistance(strA, pABegin + 1, pAEnd, strB, pBBegin + 1, pBEnd);
    } else {
        int t1 = calculateEditDistance(strA, pABegin, pAEnd, strB, pBBegin + 1, pBEnd);
        int t2 = calculateEditDistance(strA, pABegin + 1, pAEnd, strB, pBBegin, pBEnd);
        int t3 = calculateEditDistance(strA, pABegin + 1, pAEnd, strB, pBBegin + 1, pBEnd);
        return min(min(t1, t2), t3) + 1;
    }
}

//dp
int minDistance(string word1, string word2) {
    size_t len1 = word1.length();
    size_t len2 = word2.length();
    
    int dp[len1 + 1][len2 + 1];
    memset(dp, 0, sizeof(dp));
    
    for (int i = 0; i <= len1; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= len2; j++) {
        dp[0][j] = j;
    }
    
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + dp[i - 1][j - 1];
                dp[i][j] = min(dp[i][j], min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
            }
        }
    }
    return dp[len1][len2];
}

bool isOneEditDistance(string s, string t) {
    if (s.size() < t.size()) {
        swap(s, t);
    }
    size_t m = s.size();
    size_t n = t.size();
    size_t diff = m - n;
    
    if (diff >= 2) {
        return false;
    } else if (diff == 1) {
        for (int i = 0; i < n; ++i) {
            if (s[i] != t[i]) {
                return s.substr(i + 1) == t.substr(i);
            }
        }
        return true;
    } else {
        int cnt = 0;
        for (int i = 0; i < m; ++i) {
            if (s[i] != t[i]) {
                ++cnt;
            }
        }
        return cnt == 1;
    }
}

#pragma mark - bianry Tree
#pragma mark - tree
bool insert(TreeNode *root, int val) {
    if (root == nullptr)
    {
        return false;
    }

    TreeNode *newNode = new TreeNode(val);
    if (newNode == nullptr)
    {
        return false;
    }
    TreeNode *p = root;

    while (p) {
        if (p->val > val)
        {
            if (p->left == nullptr)
            {
                p->left = newNode;
                return true;
            }
            p = p->left;
        } else {
            if (p->right == nullptr)
            {
                p->right = newNode;
                return true;
            }
            p = p->right;
        }
    }
    return true;
}
// size_t get_node_count(TreeNode *root);
// void print_values(TreeNode *root);
// bool delete_tree(TreeNode *root);
bool is_in_tree(TreeNode *root, int val) {
    if (root == nullptr)
    {
        return false;
    }
    TreeNode *p = root;
    while (p) {
        if (p->val > val)
        {
            p = p->left;
        } else if (p->val < val) {
            p = p->right;
        } else {
            return true;
        }
    }

    if (p == nullptr)
    {
        return false;
    }
    return true;
}
// int get_height(TreeNode *root);
int get_min(TreeNode *root) {
    if (root == nullptr)
    {
        return -1;
    }

    int result = INT_MAX;
    TreeNode *p = root;
    while (p) {
        if (p->left && p->left->val < result)
        {
            result = p->left->val;
            p = p->left;
        }
    }
    return result;
}

int get_max(TreeNode *root) {
    if (root == nullptr)
    {
        return -1;
    }

    int result = INT_MIN;
    TreeNode *p = root;
    while (p) {
        if (p->right && p->right->val < result)
        {
            result = p->right->val;
            p = p->right;
        }
    }
    return result;
}
// bool is_binary_search_tree(TreeNode *root);
// bool delete_value(TreeNode *root, int value);
// int get_successor(TreeNode *root, int value);
// int get_predecessor(TreeNode *root, int value);
